// hdu3633
// 题意：
// 给定一个n*m(<=8*8)的棋盘，一些格子已经被染成了黑色和白色，每个格子都有
// 一个权值0或-1或1。现在要将所有格子染色，使得黑色的构成一个联通块，
// 白色的构成一个联通块，并且没有一个2*2的同色正方形，
// 求使得 |黑色权值和-白色权值和| 最小的结果，输出这个最小值下的染色方案数，
// 并随意输出一种方案。
//
// 题解：
// 一开始想了半天关于绝对值的dp，其实只要枚举一遍最终合法状态算一下就行。
// 然后就是插头dp，论文里也讲的比较清楚，用最小表示法表示联通性。
//
// 贴一下大牛的解题报告：http://linjiazhen.is-programmer.com/posts/25989.html
//
// 如果看过cdq那篇《基于连通性状态压缩的动态规划问题》的话,可以很容易发现这是一道状态压缩DP问题,很明显的强调了连通性.
// 此题改编自Uva10532(Black & White)在原题的基础上增加的格子上的数字,要保证数字差值最小且输出总方案数,所以要在原来的基础上增加一维表示差值.
// 具体解法如下:
// 对于每个轮廓线,记录的是上方m个格子的连通性(用最小表示法记录,广义路径的用插头表示法的话讨论的状态太多)上方m个格子的颜色和左上角的颜色(用m+1位的二进制就能准确表示,其实记录左边第一个方格的颜色就能推出剩下m-1个方格的颜色,根据"相连格子不是一个连通块的话颜色不相同,是的话相同"这个显而易见的结论,这样子状态精简了很多,只用2位的二进制表示,但是状态数并没有减少,转移的系数反而增加了--要计算颜色,所以并不必要这么做),以及|sumBlack - sumWhite|.
// 由于最小表示法没办法精确存储,所以要用散列hash,或者直接map.
// 转移的时候,每个格子有一到两个填色方案
// 以黑色为例转移如下:
// If 最后一格 && 左白 && 上白 && 左上黑 Then 照成不连通,非法
// If 左黑 && 上黑 && 左上黑             Then 形成2x2的格子,非法
// If 上白 && 轮廓线上没有和上边相连的格子
// 	If 轮廓线上有白色的格子		Then 照成不连通, 非法
// 	If 当前格不是最后两格		Then 非法
// 	   (因为如果剩下格子有白色,照成不连通 剩下格子全黑色,必然有2x2的黑色格子)
// If 左黑 && 上黑			Then 合并两个连通块
// Else If 左白 && 上白		Then 形成新的连通块
// Else If 左黑 && 上白		Then 和左边的合并
// Else If 左白 && 上黑		Then 和上边的合并
// 最后对所有状态判断一下最多只能存在两个连通块
// 至于输出一个方案的话只要每次记录这个状态是从哪转来的,另外开两个数组记录前驱和当前颜色就好了.
// 
// 在极限情况下(8*8的矩阵全是'.',数字随机)测了200组,最大的状态有180W,单个格子最大的状态7W. 
//
// run: $exec < input
// opt: 0
// flag: -g
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

int const  inf = 1 << 30;
int const maxn = 10;
int a[maxn][maxn];
std::string g[maxn];
int pre[65][100100];
char op[65][100100];
int n, m, now, prev;

char const black = 'x';
char const white = 'o';

template <class T>
T abs(T x) { return x < 0 ? -x : x; }

struct hash_table
{
	int static const maxsize = 100007;
	int head[maxsize], next[maxsize], state[maxsize], dis[maxsize], color[maxsize], dp[maxsize];
	int size;

	void clear()
	{
		size = 0;
		std::fill(head, head + maxsize, -1);
	}

	void push(int st, int di, int co, int d, int id, int p, char ch)
	{
		int h = ((st << 6) + co + 1997 + di) % maxsize;
		for (int i = head[h]; i != -1; i = next[i]) {
			if (state[i] == st && dis[i] == di && color[i] == co) {
				dp[i] += d;
				return;
			}
		}
		state[size] = st; dis[size] = di; color[size] = co; dp[size] = d;
		pre[id][size] = p; op[id][size] = ch;
		next[size] = head[h]; head[h] = size++;
	}
};

hash_table f[2];

int code[10];
// using minimum representation to encode
int encode()
{
	std::vector<int> tmp(10, -1);
	int st = 0;
	for (int i = 0, count = 0; i < m; i++) {
		if (tmp[code[i]] == -1) tmp[code[i]] = count++;
		st = (st << 3) | tmp[code[i]];
	}
	return st;
}

void decode(int st)
{
	for (int i = m - 1; i >= 0; i--, st >>= 3) code[i] = st & 7;
}

void dp(int i, int j, int c)
{
	for (int t = 0; t < f[prev].size; t++) {
		int color = f[prev].color[t];
		int up = i ? ((color >> j) & 1) == c : 0;
		int left = j ? ((color >> (j - 1)) & 1) == c : 0;
		int lu = i && j ? (color >> m) == c : 0;
		// 2 * 2 square
		if (up && left && lu) continue;
		if (i == n - 1 && j == m - 1 && !up && !left && lu) continue;
		decode(f[prev].state[t]);

		if (i && !up) {
			// count1 for connectivity with up
			// count2 for count on proile same color with up
			int count1 = 0, count2 = 0;
			for (int k = 0; k < m; k++) {
				if (code[k] == code[j]) count1++;
				if (((color >> k) & 1) != c) count2++;
			}
			// no grid connect with up
			if (count1 == 1) {
				// there are grids same color with up, cannot be connected
				if (count2 > 1) continue;
				// if current grid is not the last two grid, then illegal
				if (i < n - 1 || j < m - 2) continue;
			}
		}

		if (left && up) {
			// merge two connected component
			if (code[j] != code[j - 1])
				for (int k = 0, x = code[j]; k < m; k++)
					if (code[k] == x) code[k] = code[j - 1];
		} else if (left && !up)
			code[j] = code[j - 1];
		else if (!left && !up)
			code[j] = m;

		// update left-up grid color for next state
		if (color & (1 << j)) color |= 1 << m;
		else color &= ~(1 << m);

		if (c) color |= 1 << j;
		else color &= ~(1 << j);

		f[now].push(encode(), f[prev].dis[t] + (c ? a[i][j] : -a[i][j]), color, f[prev].dp[t], i * m + j, t, c ? 'x' : 'o');
	}
}

void print(int k)
{
	for (int i = n - 1; i >= 0; i--)
		for (int j = m - 1; j >= 0; k = pre[i * m + j--][k])
			g[i][j] = op[i * m + j][k];
	for (int i = 0; i < n; i++) std::cout << g[i] << "\n";
}

int main()
{
	std::ios::sync_with_stdio(false);
	int T; std::cin >> T;
	for (int ti = 1; ti <= T; ti++) {
		std::cout << "Case " << ti << ": ";
		std::cin >> n >> m;
		for (int i = 0; i < n; i++) std::cin >> g[i];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++) std::cin >> a[i][j];

		now = 0; prev = 1;
		f[now].clear();
		f[now].push(0, 0, 0, 1, 0, 0, 0);
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++) {
				now ^= 1; prev ^= 1;
				f[now].clear();
				if (g[i][j] != black) dp(i, j, 0);
				if (g[i][j] != white) dp(i, j, 1);
			}

		int min = inf, ans = 0, k;
		for (int i = 0; i < f[now].size; i++) {
			int count = 0;
			std::vector<int> h(10, 0);
			decode(f[now].state[i]);
			for (int j = 0; j < m; j++)
				if (!h[code[j]]) { count++; h[code[j]] = 1; }
			if (count <= 2) {
				int tmp = abs(f[now].dis[i]);
				if (tmp < min) {
					min = tmp;
					ans = f[now].dp[i];
					k = i;
				} else if (tmp == min) {
					ans += f[now].dp[i];
				}
			}
		}
		if (min >= inf) std::cout << "0 0\n";
		else {
			std::cout << min << " " << ans << "\n";
			print(k);
		}
		std::cout << "\n";
	}
}

